package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-06
 * Time:15:30
 */

import java.util.Stack;

/**
 *
 牛客算法篇:BM44 有效括号序列
 描述
 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 数据范围：字符串长度 0≤n≤100000≤n≤10000
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 示例1
 输入：
 "["
 返回值：
 false

 */
public class isValid {
    public boolean isValid (String s) {
        // write code here
        if (s.length() < 2) return false;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.empty() || stack.pop() != c) return false;
        }
        return stack.empty();
    }
}
